1. Field of the Invention
This invention relates to microprocessors, and more particularly, to branch prediction mechanisms.
2. Description of the Relevant Art
Modern day processor systems tend to be structured in multiple stages in a pipelined fashion. Typical pipelines often include separate units for fetching instructions, decoding instructions, mapping instructions, executing instructions, and then writing results to another unit, such as a register. An instruction fetch unit of a microprocessor is responsible for providing a constant stream of instructions to the next stage of the processor pipeline. Typically, fetch units utilize an instruction cache in order to keep the rest of the pipeline continuously supplied with instructions. The sequence of instructions being fetched is based upon a prediction of the program flow, which is normally sequential. However, branch instructions can change the sequential nature of program flow. Therefore, accurate prediction of branch instructions can ensure that the fetch unit continues to fetch instructions down the correct path.
Branch prediction techniques can predict an evaluation of a condition of a branch instruction and/or a branch target address. The branch prediction logic may be complex in order to provide a high accuracy. Therefore, the branch prediction logic may use multiple clock cycles to perform evaluations and calculations to produce results for the condition and the branch target address. However, during these multiple clock cycles, instructions are being fetched from the instruction cache. These fetched instructions may be flushed if the branch prediction logic determines other instructions should be fetched.
The branch prediction logic may utilize logic that trades off accuracy for faster results. However, the lower accuracy may lead to situations where instructions are fetched down the wrong path. For example, a program being executed by the processor may utilize a subroutine that gets called from multiple different locations in the code. When attempting to generate a fast branch target prediction for this subroutine, the branch prediction logic may often mispredict the next fetch program counter (PC) address since the return address is not static. These mispredictions result in a stall in the processor pipeline while the fetching of instructions is redirected and the incorrectly fetched instructions are flushed. A stall in a pipeline may prevent useful work from being performed during one or more pipeline stages. Some stalls may last several clock cycles and significantly decrease processor performance
In view of the above, improved methods and mechanisms for efficient branch prediction are desired.